package leetCode.array_and_string;

/**
 * 功能：搜索插入位置
 * 作者：lc
 * 日期：2025/2/14 3:08
 */
public class MainT001 {

    // 暴力破解
    public static int searchInsert1(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[0] > target) {
                return 0;
            }
            if (nums[i] == target) {
                return i;
            }
            if (nums[i] < target && (i + 1) < nums.length && nums[i + 1] > target) {
                return i + 1;
            }
        }
        return nums.length;
    }

    /**
     * 二分查找
     * 从有序数组中查找就可以使用二分查找，但是这里有点特殊就是需要返回插入数组下标
     * 这里主要需要考虑的就是，没有该元素应该插入到什么位置
     * 而这个又涉及到两种情况，一个尾部插入和数组中间插入
     *只有当一种情况才会导致尾部插入，就是一直nums[mid] < target
     */
    public static int searchInsert2(int[] nums, int target) {
        int left = 0;// 左边界
        int right = nums.length - 1;// 右边界
        int ans = nums.length;// 如果没有找到，则插入到数组末尾
        while (left <= right) {
            int mid = left + ((right - left) >> 1); // 防止溢出
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                ans = mid;
                right = mid - 1;
            }
        }
        return ans;
    }

        public static int searchInsert3(int[] nums, int target) {
            for(int i=0;i<nums.length;i++){
                if(nums[i]>=target) return i;
            }
            return nums.length;
        }


}
